home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6823 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c,comp.graphics.algorithms,rec.games.programmer
  4. Subject: Re: Speed question here...
  5. Date: 15 Feb 1996 07:34:47 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4fvjqnINN84p@keats.ugrad.cs.ubc.ca>
  8. References: <4ftluh$1gkv@hearst.cac.psu.edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4ftluh$1gkv@hearst.cac.psu.edu>,
  12. William Koscho <koscho@wjk130.rh.psu.edu> wrote:
  13. >I was curious as to how fast something like the 
  14. >following would execute:
  15.  
  16. I don't know? How fast can your compiler tell you that the program can't be
  17. compiled?
  18.  
  19. >    int x;
  20. >    node *ptr;   ptr in linked list
  21. >
  22. >       for ( ptr = first_node; ptr != NULL; ptr = ptr.next ) {
  23.  
  24. You don't dereference pointers by doing ptr.field. You use *(ptr).field, or,
  25. more commonly, ptr->field.
  26.  
  27.  
  28. >       for ( x = 0; x < max; x++ ) {
  29. >        array[x] = array_other[x];
  30. >           }
  31. >      } 
  32. >
  33. >I really am not interested in the assignment statement, that's easy.
  34. >but the traversal through the linked list, and inner integer incremental
  35. >for loop for each node visited.  How fast is a traversal through
  36. >a linked list when you do a for loop at each node?
  37.  
  38. How big is the for loop? The ptr variable (in a correctly coded version of the
  39. snippet that will compile when put into a proper program context) can be
  40. optimized into a register. The loop increment that passes through the array can
  41. be nothing more than just something like
  42.  
  43.     load    R1, first_node
  44. loop:    
  45.     ; do whatever
  46.  
  47.     load    R1, NEXT_OFFSET[R1]    ;    R1 = R1->next
  48.     jnz    R1, loop        ;    test R1, branch if zero
  49.  
  50. This assumes a RISC machine with only indirect addressing.
  51.  
  52. An empty inner loop (that isn't optimized away for some reason) won't have much
  53. of an effect on these instructions, but the speed of the traversal will
  54. obviously suffer if you do many iterations in the loop. The more work you do at
  55. each node, the less significant is the overhead of going through the list.
  56.  
  57. -- 
  58.  
  59.